package com.example.huffman;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.TreeSet;

/**
 * Created by Administrator on 2017/9/23 0023.
 */

public class Main {
    public static void main(String[] args) {
        System.out.println(1%2);

//        char[] c = new char[128 - 32];
//        for (int i = 0; i < 128 - 32; ++i) {
//            c[i] = (char) (i + 32);
//        }
//
//        TreeSet<ChildNode> chars = makeChars(c);
//        RootNode rootNode = buildTree(chars);
//        LinkedList<CodeTable> table = makeTable(rootNode);
//        for (CodeTable t : table) {
//            System.out.println(t);
//        }
//        StringBuilder sb1 = transcoding(table, new char[]{'b','b'});
//        System.out.println(sb1);
//        StringBuilder sb2 = decoding(rootNode, sb1);
//        System.out.println(sb2);

    }

    public static StringBuilder decoding(RootNode root, StringBuilder code) {
        char[] codes = new char[code.length()];
        for (int i = 0; i < code.length(); ++i) {
            codes[i] = code.charAt(i);
        }
        StringBuilder sb = new StringBuilder();
//        decoding(root.parentNode, root.parentNode, codes, 0, sb);
        sb = decoding(root, codes);
        return sb;
    }

    public static void decoding(ChildNode root, ChildNode childNode, char[] code, int index, StringBuilder sb) {

        if (index < code.length) {
            boolean isParent = childNode instanceof ParentNode;
            if (isParent) {
                if (code[index] == '0') {
                    decoding(root, ((ParentNode) childNode).left, code, index + 1, sb);
                } else if (code[index] == '1') {
                    decoding(root, ((ParentNode) childNode).right, code, index + 1, sb);
                } else {
                    throw new IllegalArgumentException("code should contains '0' or '1'");
                }
            } else {
                sb.append(childNode.c);
                childNode = root;
                decoding(root, childNode, code, index, sb);
            }
        }
    }


    public static StringBuilder decoding(RootNode root, char[] code) {
        StringBuilder sb = new StringBuilder();
        ChildNode node = root.parentNode;

        for(int i=0;i<code.length;++i)
        {
            if (node instanceof ParentNode) {
                ParentNode parent = (ParentNode) node;
                char c = code[i];
                if (c == '0') {
                    node = parent.left;
                } else if (c == '1') {
                    node = parent.right;
                } else {
                    throw new IllegalArgumentException("code should contains '0' or '1'");
                }
                if (!(node instanceof ParentNode)) {
                    sb.append(node.c);
                    node = root.parentNode;
                }
            } else {
                sb.append(node.c);
                node = root.parentNode;
            }
        }

        return sb;
    }
//
//    public static void appendNextSource(StringBuilder sb, ChildNode child) {
//        if ()
//    }

    public static StringBuilder transcoding(LinkedList<CodeTable> table, char[] chars) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < chars.length; ++i) {
            final char c = chars[i];
            Iterator<CodeTable> iterator = table.iterator();
            while (iterator.hasNext()) {
                CodeTable code = iterator.next();
                if (code.childNode.c == c) {
                    sb.append(code.code);
                    break;
                }
            }
        }
        return sb;
    }


    public static LinkedList<CodeTable> makeTable(RootNode root) {
        LinkedList<CodeTable> table = new LinkedList<CodeTable>();
        List<Character> codes = new ArrayList<>();
        recursionTable(root.parentNode, codes, 0, table);
        return table;
    }

    public static void recursionTable(ChildNode childNode, List<Character> codes, int index, LinkedList<CodeTable> table) {
        if (childNode instanceof ParentNode) {
            ParentNode parent = (ParentNode) childNode;
            ChildNode left = parent.left;
            if (left != null) {
                if (index < codes.size()) {
                    codes.set(index, '0');

                } else {
                    codes.add('0');
                }
                recursionTable(left, codes, index + 1, table);
            }

            ChildNode right = parent.right;
            if (right != null) {
                if (index < codes.size()) {
                    codes.set(index, '1');

                } else {
                    codes.add('1');
                }
            }
            recursionTable(right, codes, index + 1, table);
        } else {
            table.add(new CodeTable(codes, index, childNode));
        }
    }


    public static RootNode buildTree(TreeSet<ChildNode> chars) {
        while (chars.size() > 1) {
            final ChildNode first = chars.pollFirst();
            final ChildNode second = chars.pollFirst();
            ParentNode parent = new ParentNode(first, second);
            chars.add(parent);
        }
        RootNode rootNode = new RootNode();
        rootNode.parentNode = chars.pollFirst();
        return rootNode;
    }

    public static TreeSet<ChildNode> makeChars(char[] chars) {
        ChildNode[] sizes = new ChildNode[128];

        for (int i = 0; i < chars.length; ++i) {
            final char c = chars[i];
            if (sizes[c] == null) {
                sizes[c] = new ChildNode(c, 1);
            } else {
                sizes[c].n++;
            }


        }
        TreeSet<ChildNode> set = new TreeSet<>();
        for (int i = 0; i < sizes.length; ++i) {
            if (sizes[i] != null) {
                set.add(sizes[i]);
            }
        }

        return set;
    }
}
